import java.util.Arrays;
import java.util.HashSet;


public class BurrowsWheeler
{
	// apply Burrows-Wheeler encoding, reading from standard input and writing to standard output
    public static void encode()
    {
    	StringBuilder builder = new StringBuilder();
    	while(!BinaryStdIn.isEmpty())
    		builder.append(BinaryStdIn.readChar());
    	
    	final String input = builder.toString();
    	CircularSuffixArray csa = new CircularSuffixArray(input);
    	
    	final int len = input.length();
    	for(int i = 0; i < len; i++)
    		if(csa.index(i) == 0)
    		{
    			BinaryStdOut.write(i);
    			break;
    		}
    	
    	for(int i = 0; i < len; i++)
    		BinaryStdOut.write(input.charAt((len + csa.index(i) - 1) % len));
    	
    	BinaryStdOut.close();
    }

    // apply Burrows-Wheeler decoding, reading from standard input and writing to standard output
    public static void decode()
    {
    	int first = BinaryStdIn.readInt();
    	
    	final StringBuilder builder = new StringBuilder();
    	while(!BinaryStdIn.isEmpty())
    		builder.append(BinaryStdIn.readChar());
    	
    	final String input = builder.toString();
    	final char[] t = input.toCharArray();
    	final char[] w = input.toCharArray();
    	Arrays.sort(w);
    	
    	int[] counts = new int[256];
    	for(int i = 0; i < w.length; i++)
    		counts[w[i]]++;
    	
    	int[][] positions = new int[256][];
    	for(int i = 0; i < 256; i++)
    		positions[i] = new int[counts[i]];
    	
    	int[] offsets = new int[256];
    	for(int i = 0; i < t.length; i++)
    		positions[t[i]][ offsets[t[i]]++ ] = i;

    	for(int i = 0; i < 256; i++)
    		offsets[i] = 0;
    	
    	int[] next = new int[t.length];
    	
    	for(int i = 0; i < t.length; i++)
    		next[i] = positions[ w[i] ] [ offsets[w[i]]++ ];
    	
    	for(int i = 0, n = first; i < t.length; i++, n = next[n])
    		BinaryStdOut.write(w[n]);
    	
    	BinaryStdOut.close();
    }

    // if args[0] is '-', apply Burrows-Wheeler encoding
    // if args[0] is '+', apply Burrows-Wheeler decoding
    public static void main(String[] args)
    {
    	if("-".equals(args[0]))
    		encode();
    	else
    		decode();
    }
}
